#include <iostream>
#include <limits>
using namespace std;

size_t Left(size_t n)
{
	return n * 2 + 1;
}

size_t Right(size_t n)
{
	return n * 2 + 2;
}

size_t Parent(size_t n)
{
	return n / 2;
}

template<typename T, size_t n>
void MaxHeapIFY(T(*arr)[n], size_t Largest, size_t sz = n)
{
	int parent;
	do
	{
		size_t left = Left(Largest);
		size_t right = Right(Largest);
		parent = Largest;

		if (left <= sz && (*arr)[left] > (*arr)[Largest])
			Largest = left;
		if (right <= sz && (*arr)[right] > (*arr)[Largest])
			Largest = right;

	} while (Swap(arr, parent, Largest));
}

template<typename T, size_t n>
bool Swap(T(*arr)[n], size_t i, size_t Largest)
{
	if (i != Largest)
	{
		std::swap((*arr)[i], (*arr)[Largest]);
		return true;
	}
	return false;
}

template<typename T, size_t n>
void BuildMaxHeap(T(*arr)[n], int sz = n / 2)
{
	for (; sz >= 0; --sz)
		MaxHeapIFY(arr, sz);
	//倒序遍历为什么呢？
}

template<typename T, size_t n>
void HeapSort(T(*arr)[n], int sz = n - 1)
{
	for (int i = sz; i > 0;)
	{
		std::swap((*arr)[i--], (*arr)[0]);
		MaxHeapIFY(arr, 0, i);
	}
}

template<typename T, size_t n>
T HeapExtractMax(T(*arr)[n], T *&ptrSz)
{
	if (ptrSz < arr[0])
		throw range_error("range index exceed!");

	cout << arr[0] << endl;

	T Max = (*arr)[0];

	(*arr)[0] = *ptrSz;
	--ptrSz;

	MaxHeapIFY(arr, 0);
	return Max;
}

template<typename T>
void HeapIncreaseKey(T *arr, T i, T Key)
{
	if (Key < arr[i])
		throw invalid_argument("Invalid IncreaseKey");

	arr[i] = Key;
	int pt = i;
	bool Sw;
	do//InsertionSort方式交换
	{
		Sw = true;
		while (arr[Parent(pt)] < arr[i] && i > 0 && pt > 0)
		{
			pt = Parent(pt);
			Sw = false;
		}
		if (pt != i)
		{
			std::swap(arr[i], arr[pt]);
			pt = i;
		}
	} while (pt == i && !Sw);
}

template<typename T, size_t n>
T *GetArrLastPoniter(T(*arr)[n], size_t sz = n)
{
	return &(*arr)[n - 1];
}

template<typename T, size_t n>
void HeapInsert(T(*arr)[n], T *&LastPtr, int Key)
{
	if (GetArrLastPoniter(arr) < LastPtr + 1)
		throw invalid_argument("Invalid IncreaseKey");
	*++LastPtr = numeric_limits<T>().min();
	HeapIncreaseKey(arr[0], LastPtr - arr[0], Key);
}
int main()
{
	int arr1[] = { 11, 21, 13, 42, 12, 16, 27 };
	BuildMaxHeap(&arr1);//建立最大堆
	//HeapSort(&arr1);//排序最大堆
	int *ptr = GetArrLastPoniter(&arr1);//用来替代heapArr->Size();
	int Max = HeapExtractMax(&arr1, ptr);
	HeapIncreaseKey(arr1, 4, 30);
	HeapInsert(&arr1, ptr, 20);
	return 0;
}
